#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include"algorithm.h"
void moveZeroes(vector<int>& nums) {
    int dst = -1;
    int cur;
    for (int i = 0; i < nums.size(); i++) {
        cur = nums[i];
        if (cur == 0) {

        }
        else {
            dst++;

            swap(nums[dst], nums[i]);

        }
    }
}

void duplicateZeros(vector<int>& arr) {
    int dst = -1, cur = 0, n = arr.size();
    while (cur < n) {
        if (arr[cur]) {
            dst++;
        }
        else {
            dst += 2;
        }
        if (dst >= n - 1) {
            break;
        }
        cur++;
    }
    if (dst == n) {
        arr[n - 1] = 0;
        dst -= 2;
        cur--;
    }
    while (cur >= 0) {
        if (arr[cur]) {
            arr[dst--] = arr[cur--];
        }
        else {
            arr[dst--] = 0;
            arr[dst--] = 0;
            cur--;
        }


    }

}

int getSum(int n) {
    int sum = 0;
    while (n) {
        int i = n % 10;
        sum += i * i;
        n /= 10;
    }
    return sum;
}
bool isHappy(int n) {
    int slow = n;
    int fast = getSum(n);
    while (slow != fast)
    {
        slow = getSum(slow);
        fast = getSum(getSum(fast));
    }
    return slow == 1;


}

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1, ret = 0;
    while (left < right) {
        int v = min(height[left], height[right]) * (right - left);
        ret = max(ret, v);
        if (height[left] < height[right]) {
            left++;
        }
        else {
            right--;
        }

    }
    return ret;

}

int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int max = nums.size();
    int sum = 0;
    for (int i = max - 1; i >= 2; i--) {
        int left = 0, right = i - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[i]) {
                sum += (right - left);
                right--;
            }
            else {
                left++;
            }
        }
    }
    return sum;

}

vector<int> twoSum(vector<int>& price, int target) {
    int right = price.size() - 1, left = 0;

    while (left < right) {
        if (price[left] + price[right] < target) {
            left++;
        }
        else if (price[left] + price[right] > target) {
            right--;
        }
        else {
            return { price[left],price[right] };
        }
    }
    return { -1,-1 };

}

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());

    int n = nums.size();

    vector<vector<int>> vv;
    for (int keyi = 0; keyi < n;) {
        if (nums[keyi] > 0) {
            break;
        }
        int left = keyi + 1, right = n - 1;
        int target = -nums[keyi];
        while (left < right) {
            int sum = nums[right] + nums[left];
            if (sum > target)  right--;

            else if (nums[right] + nums[left] < target)   left++;

            else {
                vv.push_back({ nums[keyi],nums[left],nums[right] });
                left++; right--;
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            }
        }
        keyi++;

        while (keyi < n && nums[keyi] == nums[keyi - 1]) {
            keyi++;
        }

    }
    return vv;
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> vv;
    for (int i = 0; i < nums.size();) {

      

        for (int j = i + 1; j < nums.size();) {
            int left = j + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];

                if (sum > target) {
                    right--;
                }
                else if (sum < target) {
                    left++;
                }
                else if (sum == target) {
                    vv.push_back({ nums[i],nums[j],nums[left],nums[right] });
                    left++; right--;
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }

                }

            }
            j++;
            while (j < nums.size() && nums[j] == nums[j - 1]) {
                j++;
            }


        }
        i++;
        while (i < nums.size() && nums[i] == nums[i - 1]) {
            i++;
        }
    }
    return vv;


};

int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size(), sum = 0, len = INT_MAX;
    for (int left = 0, right = 0; right < n; right++) {
        sum += nums[right];
        while (sum >= target) {
            len = min(len, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return len == INT_MAX ? 0 : len;
}

int lengthOfLongestSubstring(string s) {
    int a[128] = { 0 };
    int left = 0, right = 0, n = s.size();
    int len = 0;
    while (right < n) {
        a[s[right]]++;

        while (a[s[right]] > 1)
        {
            a[s[left]]--;
            left++;
        }


        len = max(len, right - left + 1);
        right++;
    }
    return len;

}

int longestOnes(vector<int>& nums, int k) {
    int left = 0, right = 0, len = 0;
    int n = nums.size();
    int zero = 0;
    while (right < n) {
        if (nums[right] == 0)zero++;


        while (zero > k)
            if (nums[left++] == 0)
                zero--;


        len = max(len, right - left + 1);
        right++;
    }


    return len;
}

int minOperations(vector<int>& nums, int x) {
    int left = 0, right = 0, sum = 0;
    for (auto a : nums) {
        sum += a;
    }
    int target = sum - x;
    if (target < 0) return -1;
    int ret = -1;
    int n = nums.size();
    int tmp = 0;
    while (right < n) {
        tmp += nums[right];
        while (tmp > target) {
            tmp -= nums[left++];
        }
        if (tmp == target) {
            ret = max(ret, right - left + 1);
        }
        right++;
    }
    if (ret == -1)return ret;
    else return n - ret;

}

int totalFruit(vector<int>& fruits) {
    int left = 0, right = 0, len = 0;
    int hash[100001] = { 0 };
    for (int kinds = 0; right < fruits.size(); right++) {
        if (hash[fruits[right]] == 0) kinds++;
        hash[fruits[right]]++;

        while (kinds > 2) {
            hash[fruits[left]]--;
            if (hash[fruits[left]] == 0)kinds--;
            left++;
        }
        len = max(len, right - left + 1);
    }
    return len;

};


vector<int> findAnagrams(string s, string p) {
    int ns = s.size(), np = p.size();
    vector<int> v;
    int hashs[126] = { 0 }, hashp[126] = { 0 };
    for (auto e : p)hashp[e]++;
    for (int left = 0, right = 0, count = 0; right < ns; right++)
    {
        hashs[s[right]]++;
        if (hashs[s[right]] <= hashp[s[right]])count++;
        while (right - left + 1 > np)
        {

            if (hashs[s[left]] <= hashp[s[left]]) count--;
            hashs[s[left++]]--;
        }
        if (count == np) v.push_back(left);

    }
    return v;
}

vector<int> findSubstring(string s, vector<string>& words) {

    unordered_map<string, int> hashw;
    for (auto& s : words) hashw[s]++;

    vector<int> v;

    int len = words[0].size(), m = words.size();

    for (int i = 0; i < len; i++)
    {
        unordered_map<string, int> hashs;
        for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
        {
            string in = s.substr(right, len);
            hashs[in]++;
            if (hashs[in] <= hashw[in]) count++;

            if (right - left + 1 > len * m) {
                string out = s.substr(left, len);
                if (hashs[out] <= hashw[out]) count--;
                hashs[out]--;
                left += len;
            }
            if (count == m) v.push_back(left);

        }

    }
    return v;

}

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (right - left) / 2 + left;
        if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;


}

vector<int> searchRange(vector<int>& nums, int target) {
    if (nums.size() == 0) return { -1,-1 };
    int begin = 0;
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)left = mid + 1;
        else right = mid;
    }
    if (nums[left] != target)return { -1,-1 };
    else begin = left;

    int end = 0;
    left = 0; right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (nums[left] <= target) left = mid;
        else right = mid - 1;
    }
    return { begin,right };

}